import java.util.Arrays;


public class test {
    // leetcode 376.摆动序列(贪心优化)
    // 1. 动态规划解法
    public int wiggleMaxLength1(int[] nums) {
        int n = nums.length;
        // 1. 创建dp表
        // 存在两种状态(递增态)(递减态)
        // [0]代表以当前值为最后一个数,下次递增
        // [1]代表以当前值为最后一个数,下次递减
        int[][] dp = new int[n][2];
        // 2. 初始化
        dp[0][0] = 1;
        dp[0][1] = 1;
        // 3. 填表
        for(int i = 1;i < n;i++){
            if(nums[i] > nums[i - 1]){
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][1];
            }else if(nums[i] < nums[i - 1]){
                dp[i][1] = dp[i - 1][0] + 1;
                dp[i][0] = dp[i - 1][0];
            }else {
                dp[i][1] = dp[i - 1][1];
                dp[i][0] = dp[i - 1][0];
            }
        }
        // 4. 返回值
        return Math.max(dp[n - 1][0],dp[n - 1][1]);
    }
    // 2. 贪心解法
    public int wiggleMaxLength(int[] nums) {
        // 为了找出最长摆动序列,就要防止"提前选择到错的数"
        // 如:{1,2,3,4,2,1,3},最长应为{1,4,1,3},但如果选了{1,2...},就会导致遇到后续2时不递减
        // 为了避免这种情况,应该"递增时选最大,递减时选最小" -> ***(最长长度 = 单调性变化次数)***,
        // 从而保证"下一次选取时能够最大限度找到(比最大值小)或(比最小值大)的节点"
        int num = 1;
        int len = nums.length;
        if(len == 1){
            return num;
        }
        int index = 1;
        int flg = 0;//(标记当前为上升还是下降:1 up ; -1 down)
        // 不越界的情况下,相等就继续找
        while(index < len && nums[index - 1] == nums[index]){
            index++;
        }
        // 全是一个数
        if(index == len){
            return num;
        }
        if(nums[index - 1] > nums[index]){
            flg = 1;
        }else {
            flg = -1;
        }
        for(int i = 1;i < len;i++){
            if(nums[i] > nums[i - 1] && flg == -1){
                flg = 1;
                num++;
            }else if(nums[i] < nums[i - 1] && flg == 1) {
                flg = -1;
                num++;
            }
        }
        return num;
    }
    // leetcode 300.最长递增子序列
    // 1. 动态规划
    // 常规思路,以i位置为结尾,最长子序列的长度
    // 当以i为结尾时,遍历(1 ~ i-1)为结尾的最长子序列
    // 找到其中(小于当前值)且(最长)的dp[j] + 1,与当前的dp[i]取max
    public int lengthOfLIS1(int[] nums) {
        int n = nums.length;
        int max = 1;
        int[] dp = new int[n + 1];
        Arrays.fill(dp,1);
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < i;j++){
                if(nums[i - 1] > nums[j - 1]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }
    // 2. 动态规划 + 贪心
    // 动态规划中,通过"当前元素"与"之前元素"进行比较,找到"结尾小于当前元素的最长子序列"
    // 那么,也就是说当我们要进行拼接时,我们希望(相等长度的子序列中,末尾值尽可能小)
    // 以此才能够找到"结尾小于当前元素的最长子序列".
    // 所以我们可以通过一个数组来存储(特定长度的最长子序列中,最小的末尾值)
    // 而由于每次拼接时,该值都必须大于("小于当前长度的子序列"中的末尾值)
    // 从而保证了(长度1,长度2...)为有序的,同时下标也是有序的,即可(二分查找)
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 1];
        // -10001代表还不存在该长度的子序列
        Arrays.fill(arr,-10001);
        arr[1] = nums[0];
        int max = 1;
        for(int i = 2;i <= n;i++){
            int temp = nums[i - 1];
            int left = 0;
            int right = i - 1;
            // 相当于"偏右的二分查找",找到最长长度
            while(left < right){
                int mid = left + (right - left + 1) / 2;
                if(arr[mid] == -10001 || arr[mid] >= temp){
                    right = mid - 1;
                }else {
                    left = mid;
                }
            }
            // 存到该长度+1的位置(如果不存在,直接存;如果存在,记录最小的)
            if(arr[left + 1] == -10001){
                arr[left + 1] = temp;
            }else {
                arr[left + 1] = Math.min(arr[left + 1],temp);
            }
            max = Math.max(max,left + 1);
        }
        return max;
    }
}